A*

The A* algorithm is a simple yet elegant way of efficiently finding the lowest cost path from start to goal. In this exercise, you'll find the lowest cost plan by considering the cost of each partial plan and the value of the heuristic for all possible destinations at each step along the way.

In this exercise, you'll use a Python priority queue, which is a convenient way of maintaining a sorted queue. The PriorityQueue data structure allows you to quickly and efficiently select the lowest cost partial plan from your queue of all partial plans.

A* Exercise

Your first TODO in the exercise below is to define a heuristic. You can use the Euclidean or Manhattan distance described in the previous video or think of another alternative but keep in mind your heuristic must be admissible and consistent. You'll also define a cost for each action and modify to include diagonal actions if you like. Finally, you'll update the cost of each partial plan to reflect the sum of the cost of all actions in the plan plus the heuristic value.

Good luck! And for a peek at our solution scroll down to the link at the bottom of the notebook.